package com.example.leetcode;

class Solution {
    public boolean isMatch(String ss, String pp) {
        //dp[i][j] : [0...j]区间内的p字符串能够匹配[0...i]区间内的字符串s
        int m = ss.length();
        int n = pp.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        ss = " " + ss;
        pp = " " + pp;
        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();
        //1.状态转移方程
        //p[j]是普通字符
        //dp[i][j] = p[j]==s[i] && dp[i-1][j-1]
        //p[j] 是 .
        //dp[i][j] = dp[i-1][j-1]
        //p[j] 是 *
        //p[j-1] 是 .
        //     匹配空 : dp[i][j-2]
        //     匹配一个保留 : dp[i-1][j]
        //p[j-1] 是 普通字符
        //     匹配空 dp[i][j-2];
        //     匹配一个保留 p[j-1] == s[i] dp[i-1][j]
        // 总结
        // 1. (p[j]==s[i] || p[j]==.)&& dp[i-1][j-1]
        // 2. p[j] == * && (dp[i][j-2] || ((p[j-1]==s[i] || p[j-1] =='.')&&dp[i-1][j]))
        // 2. 初始化
        // dp[0][j] =


        dp[0][0] = true;
        for (int j = 1; j <= n; ++j) {
            // x*x*x*x*x*x*x*xx
            if (j % 2 == 0 && p[j] != '*') {
                dp[0][j - 1] = false;
                break;
            }
            dp[0][j] = true;
        }
        //3.填表顺序
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p[j] == '*') {
                    dp[i][j] = dp[i][j - 2] || ((p[j - 1] == s[i] || p[j - 1] == '.') && dp[i - 1][j]);
                } else {
                    dp[i][j] = (p[j] == s[i] || p[j] == '.') && dp[i - 1][j - 1];
                }
            }
        }
        //4.返回值
        return dp[m][n];
    }
}